package 动态规划9月;

public class 链表430扁平化多级双向链表0924 {


class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};

// https://www.bilibili.com/video/BV1bp4y1q7rD?from=search&seid=15830269803685735245&spm_id_from=333.337.0.0
    class Solution {
        public Node flatten(Node head) {
            Node res=head;
            while(head!=null){
                if(head.child!=null){
                    //1.next->child.next
                    Node next=head.next;
                    Node child=head.child;
                    while(child.next!=null){
                        child=child.next;
                    }
                    child.next=next;
                    if(next!=null){
                        next.prev=child;
                    }
                    //2.head.child->head.next
                    head.next=head.child;
                    head.child.prev=head;
                    //head.child=null
                    head.child=null;
                }
                head=head.next;
            }
            return res;
        }
    }
}
